|
Language identification in the limit is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title In this model, a learner is provided with presentation (i.e. strings) of some formal language. The learning is seen as an infinite process. Each time an element of the presentation is read the learner should provide a representation (e.g. a formal grammar) for the language. It is said that a learner can identify in the limit a class of languages if given any presentation of any language in the class the learner will produce only a finite number of wrong representations, and therefore converge on the correct representation in a finite number of steps, without however necessarily being able to announce its correctness since a counterexample to that representation could appear as an element arbitrarily long after. Gold defined two types of presentations: * Text (positive information): an enumeration of all strings the language consists of. * Complete presentation (positive and negative information): an enumeration of all possible strings, each with a label indicating if the string belongs to the language or not. ==Learnability== This model is an early attempt to formally capture the notion of learnability. Gold's paper〔p.457〕 introduces for contrast the stronger models * ''Finite identification'' (where the learner has to announce correctness after a finite number of steps), and * ''Fixed-time identification'' (where correctness has to be reached after an apriori-specified number of steps). A weaker formal model of learnability is the ''Probably approximately correct learning (PAC)'' model, introduced by Leslie Valiant in 1984. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Language identification in the limit」の詳細全文を読む スポンサード リンク
|